home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 1.iso / desktop / winmaze4.zip / SQRMAZE.CPP < prev    next >
C/C++ Source or Header  |  1994-05-03  |  25KB  |  630 lines
  1. #include <owl\owlpch.h>
  2. #include <owl\applicat.h>
  3. #include <owl\framewin.h>
  4. #include <owl\dc.h>
  5. #include "oracle.h"
  6. #include "cell.h"
  7. #include "sqrmaze.h"
  8.  
  9. #ifndef TRUE
  10. #define TRUE -1
  11. #endif
  12. #ifndef FALSE
  13. #define FALSE 0
  14. #endif
  15.  
  16. typedef cell *cell_ptr;
  17.  
  18. sqrmaze::sqrmaze(int row_count,int column_count,int thickness_of_wall,
  19.  char *seed,TFrameWindow *win_ptr)
  20. //      Contruct a maze having "row_count" rows and "column_count" columns of
  21. // rooms.  The walls should be "thickness_of_wall" (bricks) thick.  A different
  22. // (8 character of less) "seed" generally yields a different maze.
  23.   {
  24.     struct
  25.       {
  26.          int row_num;
  27.          int column_num;
  28.       }  delta [4];
  29.     int  mud_filled_room_found;
  30.     struct
  31.       {
  32.          int row_num;
  33.          int column_num;
  34.       }  next;
  35.     char wall [24] [4];
  36.     char wall_to_check;
  37.     char wall_num;
  38.     char way_out;
  39.  
  40.     // Allocate a two dimensional array of rooms.
  41.     window_ptr=win_ptr;
  42.     num_rows=row_count;
  43.     num_columns=column_count;
  44.     if (memory_allocated=((room=new cell_ptr[num_rows]) != NULL))
  45.       {
  46.         int row_num=0;
  47.         while ((memory_allocated) && (row_num < num_rows))
  48.           if (memory_allocated=((room[row_num]=new cell [num_columns]) != NULL))
  49.             row_num++;
  50.         if (! memory_allocated)
  51.           {
  52.             while (row_num)
  53.               delete [] room[--row_num];
  54.             delete [] room;
  55.             window_ptr->MessageBox("Cannot allocate maze!",
  56.              window_ptr->GetApplication()->GetName(),
  57.              MB_OK | MB_ICONEXCLAMATION);
  58.           }
  59.       }
  60.     if (memory_allocated)
  61.       {
  62.          wall_thickness=thickness_of_wall;
  63.          // Set up the directions by which a room can be exited.
  64.          delta[0].row_num=-1;    // north
  65.          delta[0].column_num=0;
  66.          delta[1].row_num=0;     // west
  67.          delta[1].column_num=-1;
  68.          delta[2].row_num=1;     // south
  69.          delta[2].column_num=0;
  70.          delta[3].row_num=0;     // east
  71.          delta[3].column_num=1;
  72.          int order_num=0;
  73.          // Set up the 4! orders in which the wall of a room can be accessed.
  74.          for (int wall_num_1=0; wall_num_1 < 4; wall_num_1++)
  75.            for (int wall_num_2=0; wall_num_2 < 4; wall_num_2++)
  76.              if (wall_num_2 != wall_num_1)
  77.                for (int wall_num_3=0; wall_num_3 < 4; wall_num_3++)
  78.                  if ((wall_num_3 != wall_num_2)
  79.                  &&  (wall_num_3 != wall_num_1))
  80.                    for (int wall_num_4=0; wall_num_4 < 4; wall_num_4++)
  81.                      if ((wall_num_4 != wall_num_3)
  82.                      &&  (wall_num_4 != wall_num_2)
  83.                      &&  (wall_num_4 != wall_num_1))
  84.                        {
  85.                          wall[order_num][wall_num_4]='\0';
  86.                          wall[order_num][wall_num_3]='\1';
  87.                          wall[order_num][wall_num_2]='\2';
  88.                          wall[order_num][wall_num_1]='\3';
  89.                          order_num++;
  90.                        }
  91.          order_selector=new oracle(&seed[0],order_num);
  92.          row_selector=new oracle(&seed[0],num_rows);
  93.          column_selector=new oracle(&seed[0],num_columns); 
  94.          int finished=FALSE;
  95.          // Generate mazes until you have one that is hard to solve.
  96.          do
  97.            {
  98.               // Pick a starting room.
  99.               first.row_num=row_selector->random_number();
  100.               first.column_num=column_selector->random_number();
  101.               current.row_num=first.row_num;
  102.               current.column_num=first.column_num;
  103.               // Excavate the starting room.
  104.               room[current.row_num][current.column_num].mark_floor(' ');
  105.               // Pick the order in which the walls of the starting room will be
  106.               // considered.
  107.               room[current.row_num][current.column_num].set_order(
  108.                order_selector->random_number());
  109.               // Excavate rooms until there are no more to excavate.
  110.               do
  111.                 {
  112.                    mud_filled_room_found=FALSE;
  113.                    // Find an adjacent room (not yet considered) that needs
  114.                    // excavating.
  115.                    do
  116.                      {
  117.                         wall_num=room[current.row_num][
  118.                          current.column_num].next_wall_num();
  119.                         if (wall_num < '\4')
  120.                           {
  121.                              wall_to_check=wall[room[current.row_num][
  122.                               current.column_num].order_to_check()][wall_num];
  123.                              if (room[current.row_num][
  124.                               current.column_num].wall_up(wall_to_check))
  125.                                {
  126.                                   next.row_num=current.row_num
  127.                                    +delta[wall_to_check].row_num;
  128.                                   if ((next.row_num >= 0)
  129.                                   &&  (next.row_num < num_rows))
  130.                                     {
  131.                                       next.column_num=current.column_num
  132.                                        +delta[wall_to_check].column_num;
  133.                                       if ((next.column_num >= 0)
  134.                                       &&  (next.column_num < num_columns))
  135.                                         {
  136.                                            if (room[next.row_num][
  137.                                             next.column_num].mark() 
  138.                                             == 'M')
  139.                                              mud_filled_room_found=TRUE;
  140.                                         }
  141.                                     }
  142.                                }
  143.                           }
  144.                      }
  145.                    while ((wall_num < '\4')
  146.                    &&     (! mud_filled_room_found));
  147.                    if (mud_filled_room_found)
  148.                    // an adjacent room needs excavating
  149.                      {
  150.                         // Exit the current room, knocking down a wall.
  151.                         room[current.row_num][
  152.                          current.column_num].knock_down_wall(wall_to_check);
  153.                         way_out=char(((int) wall_to_check+2)%4);
  154.                         // Enter the adjacent room, knocking down a wall.
  155.                         room[next.row_num][next.column_num].knock_down_wall(
  156.                          way_out);
  157.                         // Record how to return to the previous room.
  158.                         room[next.row_num][next.column_num].set_way_out(
  159.                          way_out);
  160.                         current.row_num=next.row_num;
  161.                         current.column_num=next.column_num;
  162.                         // Excavate the room.
  163.                         room[current.row_num][current.column_num].mark_floor(
  164.                          ' ');
  165.                         // Select the order in which the walls of the room will
  166.                         // be considered.
  167.                         room[current.row_num][current.column_num].set_order(
  168.                          order_selector->random_number());
  169.                      }
  170.                    else
  171.                    // no adjacent room needs excavating
  172.                      {
  173.                         if ((first.row_num != current.row_num)
  174.                         ||  (first.column_num != current.column_num))
  175.                         // not in starting room
  176.                           {
  177.                              // Go back to the room from which you entered
  178.                              // the current room.
  179.                              next.row_num=current.row_num+delta[
  180.                               room[current.row_num][
  181.                               current.column_num].way_back()].row_num;
  182.                              next.column_num=current.column_num+delta[
  183.                               room[current.row_num][
  184.                               current.column_num].way_back()].column_num;
  185.                              current.row_num=next.row_num;
  186.                              current.column_num=next.column_num;
  187.                           }
  188.                      }
  189.                 }
  190.               while ((first.row_num != current.row_num)
  191.               ||     (first.column_num != current.column_num)
  192.               ||     (wall_num < '\4'));
  193.               if (maze_okay()) // Maze is hard to solve.
  194.                 finished=TRUE;
  195.               else             // Prepare to try another maze.
  196.                 for (int row_num=0; row_num < num_rows; row_num++)
  197.                   for (int column_num=0; column_num < num_columns; column_num++)
  198.                     room[row_num][column_num].reinitialize();
  199.            }
  200.          while (! finished);
  201.          // Knock down walls blocking the entrance and exit to the maze.
  202.          room[0][0].knock_down_wall(0);
  203.          room[num_rows-1][num_columns-1].knock_down_wall(2);
  204.  
  205.          delete column_selector;
  206.          delete row_selector;
  207.          delete order_selector;
  208.       }
  209.   }
  210.  
  211. sqrmaze::~sqrmaze()
  212.   {
  213.     if (memory_allocated)
  214.       {
  215.         // Free the two dimensional array of rooms.
  216.         for (int row_num=0; row_num < num_rows; row_num++)
  217.           delete [] room[row_num];
  218.         delete [] room;
  219.       }
  220.   }
  221.  
  222. int sqrmaze::maze_okay()
  223.   {
  224.     int  adjacency;
  225.     struct
  226.       {
  227.          int row_num;
  228.          int column_num;
  229.       }  delta [4];
  230.     struct
  231.       {
  232.          int row_num;
  233.          int column_num;
  234.       }  next;
  235.     int  num_rooms_in_solution;
  236.     int  passage_found;
  237.     struct
  238.       {
  239.          int row_num;
  240.          int column_num;
  241.       }  previous;
  242.     int  result;
  243.     struct
  244.       {
  245.          int row_num;
  246.          int column_num;
  247.       }  saved;
  248.     char wall_to_check;
  249.     char way_out;
  250.  
  251.     // Set up the directions by which a room can be exited.
  252.     delta[0].row_num=-1;    // north
  253.     delta[0].column_num=0;
  254.     delta[1].row_num=0;     // west
  255.     delta[1].column_num=-1;
  256.     delta[2].row_num=1;     // south
  257.     delta[2].column_num=0;
  258.     delta[3].row_num=0;     // east
  259.     delta[3].column_num=1;
  260.     // Solve the maze.
  261.  
  262.     // Start at the entrance.
  263.     current.row_num=0;
  264.     current.column_num=0;
  265.     // Mark the room as part of the solution.
  266.     room[current.row_num][current.column_num].mark_floor('S');
  267.     num_rooms_in_solution=1;
  268.     // Prepare to consider all the walls of the room.
  269.     room[current.row_num][current.column_num].zero_wall_to_check();
  270.     // Try rooms until you get to the exit.
  271.     do
  272.       {
  273.         // Find a passage (not yet considered) out of the current room leading
  274.         // to a room not part of the proposed solution.
  275.         passage_found=FALSE;
  276.         do
  277.           {
  278.             wall_to_check
  279.              =room[current.row_num][current.column_num].next_wall_num();
  280.             if (wall_to_check < '\4')
  281.               {
  282.                  if (! (room[current.row_num][
  283.                   current.column_num].wall_up(wall_to_check)))
  284.                    {
  285.                       next.row_num=current.row_num
  286.                        +delta[wall_to_check].row_num;
  287.                       if ((next.row_num >= 0)
  288.                       &&  (next.row_num < num_rows))
  289.                         {
  290.                           next.column_num=current.column_num
  291.                            +delta[wall_to_check].column_num;
  292.                           if ((next.column_num >= 0)
  293.                           &&  (next.column_num < num_columns))
  294.                             {
  295.                                if (room[next.row_num][
  296.                                 next.column_num].mark() 
  297.                                 == ' ')
  298.                                  passage_found=TRUE;
  299.                             }
  300.                         }
  301.                    }
  302.               }
  303.           }
  304.         while ((! passage_found) && (wall_to_check < '\4'));
  305.         if (passage_found)
  306.         // passage to room not currently part of proposed solution found
  307.           {
  308.             // Enter the room.
  309.             current.row_num=next.row_num;
  310.             current.column_num=next.column_num; 
  311.             // Record the way back to the previous room.
  312.             way_out=char(((int) wall_to_check+2)%4);
  313.             room[current.row_num][current.column_num].set_way_out(way_out);
  314.             // Mark the room as part of the proposed solution.
  315.             room[current.row_num][current.column_num].mark_floor('S');
  316.             num_rooms_in_solution++;
  317.             // Prepare to consider all the walls of the room.
  318.             room[current.row_num][current.column_num].zero_wall_to_check();
  319.           }
  320.         else
  321.         // dead end
  322.           {
  323.             // Mark current room as not part of proposed solution.
  324.             room[current.row_num][current.column_num].mark_floor(' ');
  325.             num_rooms_in_solution--;
  326.             // Go back to the room from which this room was entered.
  327.             next.row_num=current.row_num+delta[
  328.              room[current.row_num][current.column_num].way_back()].row_num;
  329.             next.column_num=current.column_num+delta[
  330.              room[current.row_num][current.column_num].way_back()].column_num;
  331.             current.row_num=next.row_num;
  332.             current.column_num=next.column_num;
  333.           }
  334.       }
  335.     while((current.row_num != num_rows-1)
  336.     ||    (current.column_num != num_columns-1));
  337.  
  338.     // Now that the maze is solved, calculate the number of rooms in the
  339.     // solution (or outside the maze) that are adjacent to the rooms in
  340.     // the solution.
  341.     adjacency=0;
  342.     previous.row_num=-1;
  343.     previous.column_num=0;
  344.     current.row_num=0;
  345.     current.column_num=0;
  346.     do
  347.       {
  348.         for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
  349.           if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  350.             {
  351.                next.row_num=current.row_num+delta[wall_to_check].row_num;
  352.                if ((next.row_num >= 0)
  353.                &&  (next.row_num < num_rows))
  354.                  {
  355.                     next.column_num=current.column_num
  356.                      +delta[wall_to_check].column_num;
  357.                     if ((next.column_num >= 0)
  358.                     &&  (next.column_num < num_columns))
  359.                       {
  360.                          if (room[next.row_num][next.column_num].mark() == 'S')
  361.                            adjacency++;
  362.                       }
  363.                     else
  364.                       adjacency++;
  365.                  }
  366.                else
  367.                  adjacency++;
  368.             }
  369.           else
  370.             {
  371.                next.row_num=current.row_num+delta[wall_to_check].row_num;
  372.                if ((next.row_num >= 0)
  373.                &&  (next.row_num < num_rows))
  374.                  {
  375.                    next.column_num=current.column_num
  376.                     +delta[wall_to_check].column_num;
  377.                    if ((next.column_num >= 0)
  378.                    &&  (next.column_num < num_columns))
  379.                      {
  380.                         if ((room[next.row_num][next.column_num].mark() == 'S')
  381.                         &&  ((previous.row_num != next.row_num)
  382.                           || (previous.column_num != next.column_num)))
  383.                           {
  384.                             saved.row_num=next.row_num;
  385.                             saved.column_num=next.column_num;
  386.                           }
  387.                      }
  388.                  }
  389.             }
  390.         previous.row_num=current.row_num;
  391.         previous.column_num=current.column_num;
  392.         current.row_num=saved.row_num;
  393.         current.column_num=saved.column_num;
  394.       }
  395.     while((current.row_num != num_rows-1)
  396.     ||    (current.column_num != num_columns-1));
  397.     for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
  398.       if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  399.         {
  400.            next.row_num=current.row_num+delta[wall_to_check].row_num;
  401.            if ((next.row_num >= 0)
  402.            &&  (next.row_num < num_rows))
  403.              {
  404.                 next.column_num=current.column_num
  405.                  +delta[wall_to_check].column_num;
  406.                 if ((next.column_num >= 0)
  407.                 &&  (next.column_num < num_columns))
  408.                   {
  409.                      if (room[next.row_num][next.column_num].mark() == 'S')
  410.                        adjacency++;
  411.                   }
  412.                 else
  413.                   adjacency++;
  414.              }
  415.            else
  416.              adjacency++;
  417.         }
  418.  
  419.     // The maze is hard to solve (from the outside) if more than a third of its
  420.     // rooms are part of its solution and rooms not part of its solution tend to
  421.     // be next to rooms in its solution.
  422.     if ((3*num_rooms_in_solution >= num_rows*num_columns)
  423.     &&  (9*adjacency <= 8*num_rooms_in_solution))
  424.       result=TRUE;
  425.     else
  426.       result=FALSE;
  427.     return result;
  428.   }
  429.  
  430. int sqrmaze::external_to_maze(double x,double y)
  431. //      Return TRUE if and only if a point (x,y) is external to the maze.
  432.   {
  433.     int result;
  434.  
  435.     if (y < 0.0)
  436.       result=TRUE;
  437.     else
  438.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  439.         result=TRUE;
  440.       else
  441.         if (x < 0.0)
  442.           result=TRUE;
  443.         else
  444.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  445.             result=TRUE;
  446.           else
  447.             result=FALSE;
  448.     return result;
  449.   }
  450.  
  451. double sqrmaze::f(double x,double y)
  452. //      Return 6.0*wall_thickness if a point (x,y) is on a wall, 0.0 otherwise.
  453.   {
  454.     double z;
  455.  
  456.     if (y < 0.0)
  457.       z=0.0;
  458.     else
  459.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  460.         z=0.0;
  461.       else
  462.         if (x < 0.0)
  463.           z=0.0;
  464.         else
  465.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  466.             z=0.0;
  467.           else
  468.             {  
  469.               int tem_int=int(y);
  470.               int column_num=tem_int/(3*wall_thickness);
  471.               int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
  472.               tem_int=int(x);
  473.               int row_num=tem_int/(3*wall_thickness);
  474.               int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
  475.               if (row_num < num_rows)
  476.                 if (column_num < num_columns)
  477.                   if (x_mod_3_wall_thickness < wall_thickness)
  478.                     if (y_mod_3_wall_thickness < wall_thickness)
  479.                     // northwest corner
  480.                       z=1.0;
  481.                     else
  482.                     // north wall
  483.                       if (room[row_num][column_num].wall_up('\0'))
  484.                         z=1.0;
  485.                       else
  486.                         z=0.0;
  487.                   else
  488.                     if (y_mod_3_wall_thickness < wall_thickness)
  489.                     // west wall
  490.                       if (room[row_num][column_num].wall_up('\1'))
  491.                         z=1.0;
  492.                       else
  493.                         z=0.0;
  494.                     else
  495.                     // in room
  496.                       z=0.0;
  497.                 else
  498.                   // east most wall
  499.                   z=1.0;
  500.               else
  501.                 // south most wall
  502.                 if (column_num < num_columns)
  503.                   if (y_mod_3_wall_thickness < wall_thickness)
  504.                     // southwest corner
  505.                     z=1.0;
  506.                   else
  507.                     // south wall
  508.                     if (room[num_rows-1][column_num].wall_up('\2'))
  509.                       z=1.0;
  510.                     else
  511.                       z=0.0;
  512.                 else
  513.                   // southeast most corner
  514.                   z=1.0;
  515.             }
  516.     return z*double(6*wall_thickness);
  517.   }
  518.  
  519. int sqrmaze::part_of_solution(double x,double y)
  520. //      Return TRUE if and only if a point (x,y) is on a wall outlining the
  521. // solution to the maze.
  522.   {
  523.     int result;
  524.  
  525.     if (y < 0.0)
  526.       result=FALSE;
  527.     else
  528.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  529.         result=FALSE;
  530.       else
  531.         if (x < 0.0)
  532.           result=FALSE;
  533.         else
  534.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  535.             result=FALSE;
  536.           else
  537.             {  
  538.               int tem_int=int(y);
  539.               int column_num=tem_int/(3*wall_thickness);
  540.               int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
  541.               tem_int=int(x);
  542.               int row_num=tem_int/(3*wall_thickness);
  543.               int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
  544.               if (row_num < num_rows)
  545.                 if (column_num < num_columns)
  546.                   if (x_mod_3_wall_thickness < wall_thickness)
  547.                     if (y_mod_3_wall_thickness < wall_thickness)
  548.                       // northwest corner
  549.                       if ((room[row_num][column_num].mark() == 'S')
  550.                       ||  ((row_num > 0) 
  551.                         && (room[row_num-1][column_num].mark() == 'S'))
  552.                       ||  ((column_num > 0)
  553.                         && (room[row_num][column_num-1].mark() == 'S'))
  554.                       ||  ((row_num > 0) && (column_num > 0)
  555.                         && (room[row_num-1][column_num-1].mark() == 'S')))
  556.                         result=TRUE;
  557.                       else
  558.                         result=FALSE;
  559.                     else
  560.                       // north wall
  561.                       if (room[row_num][column_num].wall_up('\0'))
  562.                         if ((room[row_num][column_num].mark() == 'S')
  563.                         ||  ((row_num > 0)
  564.                           && (room[row_num-1][column_num].mark() == 'S')))
  565.                           result=TRUE;
  566.                         else
  567.                           result=FALSE;
  568.                       else
  569.                         result=FALSE;
  570.                   else
  571.                     if (y_mod_3_wall_thickness < wall_thickness)
  572.                     // west wall
  573.                       if (room[row_num][column_num].wall_up('\1'))
  574.                         if ((room[row_num][column_num].mark() == 'S')
  575.                         ||  ((column_num > 0)
  576.                           && (room[row_num][column_num-1].mark() == 'S')))
  577.                           result=TRUE;
  578.                         else
  579.                           result=FALSE;
  580.                       else
  581.                         result=FALSE;
  582.                     else
  583.                     // in room
  584.                       result=FALSE;
  585.                 else
  586.                   // east most wall
  587.                   if (x_mod_3_wall_thickness < wall_thickness)
  588.                     // northeast corner
  589.                     if ((room[row_num][num_columns-1].mark() == 'S')
  590.                     ||  ((row_num > 0)
  591.                       && (room[row_num-1][num_columns-1].mark() == 'S')))
  592.                       result=TRUE;
  593.                     else
  594.                       result=FALSE;
  595.                   else
  596.                     // east wall
  597.                     if (room[row_num][num_columns-1].mark() == 'S')
  598.                       result=TRUE;
  599.                     else
  600.                       result=FALSE;
  601.               else
  602.                 // south most wall
  603.                 if (column_num < num_columns)
  604.                   if (y_mod_3_wall_thickness < wall_thickness)
  605.                     // southwest corner
  606.                     if ((room[num_rows-1][column_num].mark() == 'S')
  607.                     ||  ((column_num > 0)
  608.                       && (room[num_rows-1][column_num-1].mark() == 'S')))
  609.                       result=TRUE;
  610.                     else
  611.                       result=FALSE;
  612.                   else
  613.                     // south wall
  614.                     if (room[num_rows-1][column_num].wall_up('\2'))
  615.                       if (room[num_rows-1][column_num].mark() == 'S')
  616.                         result=TRUE;
  617.                       else
  618.                         result=FALSE;
  619.                     else
  620.                       result=FALSE;
  621.                 else
  622.                   // southeast most corner
  623.                   if (room[num_rows-1][num_columns-1].mark() == 'S')
  624.                     result=TRUE;
  625.                   else
  626.                     result=FALSE;
  627.             }
  628.     return result;
  629.   }
  630.